Relazione ben fondata

In matematica, una relazione binaria R si dice ben fondata su una classe X se ogni sottoinsieme non vuoto S ⊆ X ha un elemento minimale rispetto a R, cioè un elemento m per cui, per ogni s ∈ S, non valga s R m. In altre parole, una relazione è ben fondata se:

${\displaystyle (\forall S\subseteq X)\;[S\neq \emptyset \implies (\exists m\in S)(\forall s\in S)\lnot (s\mathrel {R} m)].}$

Alcuni autori includono un'ulteriore condizione, vale a dire che R sia simile ad un insieme, cioè che gli elementi minori di un qualunque elemento dato formino a loro volta un insieme.

In modo analogo, assumendo l'assioma della scelta dipendente, una relazione è fondata quando non contiene infinite catene discendenti, il che può essere dimostrato quando non esiste una sequenza infinita x₀, x₁, x₂, ...di elementi di X tale che x_n+1 R x_n per ogni numero naturale n.^[1][2]

Nella teoria degli ordini, un ordine parziale si dice ben fondato se l'ordine parziale in senso stretto corrispondente è una relazione ben fondata. Se l'ordine è un ordine totale, la relazione si dice ben fondata.

Nella teoria degli insiemi, un insieme X è chiamato insieme ben fondato se la relazione di appartenenza all'insieme è ben fondata sulla chiusura transitiva di X. L'assioma di regolarità, che è uno degli assiomi della teoria degli insiemi di Zermelo-Fraenkel, afferma che tutti gli insiemi sono ben fondati.

Una relazione R è inversamente fondata, ascendente o noetheriana su X, se la relazione inversa R⁻¹ è ben fondata su X . In questo caso, si dice anche che R soddisfi la condizione della catena ascendente. Nel contesto dei sistemi di riscrittura, una relazione noetheriana è anche chiamata terminazione.